package com.tomatozq163.structure;

public class LoopQueue<E> implements Queue<E>{
    private E[] data;
    private int front;
    private int tail;
    private int size;
    private int capacity;

    public LoopQueue(int capacity){
        this.capacity = capacity;

        /*
        主要考虑front==tail时，表示为空
        所以故意要空一个
        ((tail+1)%c == front)时队列为满
        */
        data = (E[])new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){
        this(10);
    }

    @Override
    public void enqueue(E e) {
        //队列已满，扩容
        if ((tail+1) % data.length == front){
            resize(getCapacity()*2);
        }

        data[tail] = e;
        tail =  (tail +1 )% data.length;
        size++;
    }

    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity + 1];

        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i)%data.length];
        }

        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("cannot dequeue from an empty queue.");
        }

        E ret = data[front];
        data[front] = null;

        front = (front + 1) % data.length;
        size--;

        //当前个数为容量四分之一时才缩容
        if ((size == getCapacity() / 4)
        && (getCapacity() / 2 != 0)){
            resize(getCapacity() /2);
        }

        return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("cannot getFront from an empty queue.");
        }

        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    public int getCapacity(){
        return data.length - 1;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue:size=%d,capacity=%d\n",size,getCapacity()));
        res.append("front [");

        for (int i = front; i != tail; i = (i+1)% data.length) {
            res.append(data[i]);

            //不是最后一个
            if((i+1)%data.length != tail){
                res.append(",");
            }
        }

        res.append("] tail");

        return res.toString();
    }

    public static void main(String[] args){
        Queue<Integer> queue =new LoopQueue<>(5);

        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);

            //每入队三个，离队一个
            if ((i+1) % 3 == 0){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}
